package com.base.prefixsum;

/**
 * @ClassName SumOddLengthSubarrays
 * @Description 1588. 所有奇数长度子数组的和
 * @Author li
 * Date 2021/8/29 19:26
 * Copyright
 **/
public class SumOddLengthSubarrays {
    /**
     * 暴力法
     *
     * @param arr
     * @return
     */
    public int sumOddLengthSubarrays(int[] arr) {

        int length = arr.length;
        int ret = 0;
        for (int i = 0; i < length; ) {
            for (int j = 0; j + i < length; j++) {
                //计算每个子数组的和，可以通过前缀和优化
                ret += sumArray(arr, j, j + i);
            }
            i += 2;
        }
        return ret;
    }

    public int sumArray(int[] nums, int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += nums[i];
        }
        return sum;
    }

    /**
     * 暴力法改进，计算前缀和
     *
     * @param arr
     * @return
     */
    public int sumOddLengthSubarrays1(int[] arr) {
        int[] prefixSum = new int[arr.length+1];
        for (int i = 0; i < arr.length; i++) {
            prefixSum[i+1] = prefixSum[i] + arr[i];
        }

        int ret = 0;
        for (int i = 1; i < arr.length; i += 2) {
            for (int j = 0; j+i < arr.length; j++) {
                ret+=prefixSum[j+i] - prefixSum[j];
            }
        }
        return ret;
    }
}
